package bfs;

public class 岛屿的最大面积 {
	public static int l,r;
    public static int MAXM=51,MAXN=51;
    public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public static boolean[][] visit;
    public static int[][] queue=new int[MAXM*MAXN][2];

    //对一块岛屿及其相邻岛屿进行访问同时记录这些岛屿构成的面积
    public static int bfs(int[][] grid,int i,int j,int area){
        while(l<r){
        	//按层处理
            int size=r-l;
            area+=size;
            for(int t=0;t<size;t++){
                int nx=queue[l][0],ny=queue[l++][1];
                //枚举四个方向
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    if(x>=0&&y>=0&&x<grid.length&&y<grid[0].length&&visit[x][y]==false&&grid[x][y]==1){
                        queue[r][0]=x;
                        queue[r++][1]=y;
                        //必须在入的时候标记，而不能再拿的时候标记，否则会重复；
                        visit[x][y]=true;
                    }
                }
            }
        }
        return area;
    }
    public int maxAreaOfIsland(int[][] grid) {
        int ret=0;
        int m=grid.length;
        int n=grid[0].length;
        visit=new boolean[MAXM][MAXN];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
            	//寻找岛屿的入口
                if(grid[i][j]==1&&visit[i][j]==false){
                    l=r=0;
                    visit[i][j]=true;
                    queue[r][0]=i;
                    queue[r++][1]=j;             
                    ret=Math.max(ret,bfs(grid,i,j,0));
                }
            }
        }
        return ret;
    }
}
